Aliasing is a type of error that results from sampling, and/or from performing other approximations with respect to an original signal, such as a graphics image, audio signal, texture map data, perspective transformation data, and the like. In sound and image generation, aliasing is the generation of a false, or alias, frequency component along with the correct frequency components when performing frequency sampling. For images, aliasing produces a jagged edge, or stair-step effect. For audio, aliasing produces a buzz or noisy effect. If one has ever watched a movie and seen the wheel of a rolling wagon or car appear to be going backwards, one has witnessed aliasing. In such a case, the movie's frame rate is not adequate to describe the rotational frequency of the wheel, and our eyes are deceived by the misinformation as a result.
The Nyquist theorem states that frequency components can be successfully rendered without aliasing as long as the components do not exceed one-half the sampling frequency. Aliasing occurs for any components that exceed one-half the sampling rate.
As mentioned, aliasing can occur with respect to any sampled signal, such as an audio signal. For example, suppose an audio sine wave tone with steadily increasing frequency, from a low base tone to a high treble tone, is sampled at 48 KHz. At lower frequencies, the tone is sampled with many points per cycle. As the tone rises in frequency, though, the cycles are shorter and fewer and fewer points are available to describe it. At a frequency of 24 KHz, only two sample points are available per cycle, and the Nyquist limit has been reached. Still, in a lossless theoretical world, those two points are adequate to recreate the 24 KHz tone after conversion back to analog and low-pass filtering.
However, as the tone continues to rise above 24 KHz, the number of samples per cycle is not adequate to describe the waveform, and the inadequate description is equivalent to, or wraps to, a lower frequency tone, which creates aliasing artifacts in the reconstruction. In this regard, the tone seems to reflect around the 24 KHz point, i.e., a 25 KHz tone becomes indistinguishable from a 23 KHz tone, a 30 KHz tone becomes indistinguishable from an 18 KHz tone, etc.
In music, with its many frequencies and harmonics, aliased components mix with the real frequencies to yield a particularly obnoxious form of distortion and to generate cacophonic effects. With video, the edges of objects, and other portions of the image with high frequency content, are misrepresented, harming the quality of the picture. Thus, where the generation of an artifact free signal is desired, steps are taken from the beginning to ensure minimization of such aliasing. While area sampling has been proposed, in practice, it is hard to apply. In image processing, one sample per pixel is insufficient to avoid aliasing because there is no guarantee that the one sample sufficiently reflects all of the detail represented by the pixel space. This is so because even within the area represented by one pixel, there may be a lot of variation, particularly along the edge of some object, and so one sample is not enough for each pixel. For instance, if the center of a pixel falls right on the edge of a black box on a white background, such that half of the pixel in theory should be black and half of the pixel should be white, taking a white sample as being representative insufficiently represents the presence of the black object, and taking a black sample as being representative insufficiently represents the presence of the white background.
By taking more samples than there are pixels, the effects of aliasing can be reduced. In the above case of the black box edge on the white background and applicable two by two oversampling, if two black samples and two white samples are taken as a result, and then averaged to form one pixel value, the resulting gray pixel will better represent the image content, avoiding aliasing. Thus, oversampling and averaging is one way to minimize aliasing, or antialias the image. The same techniques work for other signals, such as audio signals. Antialiasing is the smoothing of the image or sound roughness caused by aliasing.
Since an infinite number of samples cannot be taken through oversampling, typically, the resulting frequency content of a sampled signal still contains some amount of energy above the Nyquist frequency, and thus some aliasing effects can remain even after oversampling. With sound and image data, aliases are removed by eliminating frequencies above the Nyquist frequency, or half the sampling frequency. With images, other approaches include adjusting pixel positions or setting pixel intensities so that there is a more gradual transition between the color of a line and the background color.
One way of attempting to antialias is to utilize a positive bump filter; however, bump filters introduce artifacts to the reconstructed signal. For example, utilizing a bump filter with image data can cause a blurriness or aliasing like effects. An ideal filter for removing frequencies above the Nyquist frequency is a box filter in the frequency domain (See FIG. 1A) set at the Nyquist frequency. This corresponds to a sinc filter (sin (x)/x) in the spatial domain (See FIGS. 1B and 1C). The sinc function is infinite which means that it is impossible to have a perfect reconstruction filter in the spatial domain; however, adequate approximations that discard very small values for very high x values and very low x values are useful since convolution with respect to those values makes a de minimis contribution to the end result.
However, a problem arises in connection with convolving the sinc function with a real valued signal limited to a range, which is the case for image data because pixel representations are generally limited to the range [0, 255], or [0, 65535]. The problem that arises is that the values resulting from the convolution for any given sample may be outside of the range. For instance, where pixel representation is limited to the range [0, 255], a value may result that is negative, or larger than 255.
One way of handling the resulting values that are outside of the range is to clip the values to the limits of the range. For example, for the range [0, 255], −10, −3, and −1175 would each be represented by 0 and 258, 293 and 1034 would each be represented by 255. However, this method results in artifacts being present in the reconstructed signal as well, and effectively reintroduces aliasing into the signal.
Another technique for handling this scenario is to remap the resulting range onto the original range, i.e., if the resulting range as a result of convolution with the sinc function is [−128, 383], this range could be remapped to [0, 255] by adding 128 to the value and dividing by two. In this fashion, each pixel value would again be in the range [0, 255] as a result of this range “squeezing” process. However, this technique introduces problems in the reconstructed data as well. In particular, this technique tends to have the effect of reducing contrast in the data.
Thus, an improved technique is desired for reconstructing a quality signal from point samples that avoids the persisting aliasing problems and various introductions of other artifacts in accordance with prior art techniques. Furthermore, an improved technique is desired for remapping values outside of a range back to the range, i.e., for minimizing clipping error. Still further, a method is desired which generally diffuses the error created from such a remapping process in order to minimize local error in the reconstructed signal.